interface ICompareable {
  getWeight(): number;
}

class PriorityQueue {
  private _heap: Array<ICompareable>

  constructor() {
    /// 第一个不可以使用。序号从1开始
    this._heap = [{ getWeight: function (): number { return 0 } }]
  }

  static wrap(w: number, obj: any): ICompareable {
    return {
      data: obj,
      getWeight: function (): number {
        return w
      }
    } as ICompareable
  }

  /**
   * push: O(logN)
   */
  public push(v: ICompareable): void {
    this._heap.push(v)
    this._adjustUp()
    // for (let i = 1; i < this._heap.length; i = i + 1) {
    //   console.log(this._heap[i].getWeight())
    // }
  }

  /**
   * pop: O(logN)
   * 权值最大者优先
   * 如果权值相等，顺序不固定（不保证是push的调用顺序）
   * 如果本队列为空将返回undefined
   */
  public pop(): ICompareable | undefined {
    if (this.isEmpty()) {
      return undefined
    }
    if (this.size() == 1) {
      return this._heap.pop()
    }

    // let tmp = this._heap[this._root()]
    // this._heap[this._root()] = this._heap[this._last()]
    // this._heap[this._last()] = tmp
    [this._heap[this._root()], this._heap[this._last()]] = [this._heap[this._last()], this._heap[this._root()]]
    let r = this._heap.pop()
    this._adjustDown()
    return r
  }

  /**
   * front: O(1)
   * 如果本队列为空将返回undefined
   */
  public front(): ICompareable | undefined {
    if (this.isEmpty()) {
      return undefined
    }
    return this._heap[this._root()]
  }

  /**
   * isEmpty
   */
  public isEmpty(): boolean {
    return this.size() == 0
  }

  /**
   * size 取本队列的大小
   */
  public size(): number {
    return this._heap.length - 1
  }

  // 将内部数组最后一个元素调整至适当位置，使得满足堆的性质
  private _adjustUp() {
    let n: number = this._last()
    while (Math.floor(n / 2) > 0) {
      let fa: number = Math.floor(n / 2)
      if (this._heap[fa].getWeight() < this._heap[n].getWeight()) {
        // let tmp = this._heap[fa]
        // this._heap[fa] = this._heap[n]
        // this._heap[n] = tmp
        [this._heap[fa], this._heap[n]] = [this._heap[n], this._heap[fa]]
        n = fa
      } else {
        break
      }
    }

  }

  // 将内部数组第一个元素调整至适当位置，使得满足堆的性质
  private _adjustDown() {
    let n: number = this._root()
    while (2 * n < this._heap.length) {
      let lb = 2 * n
      let toSwap = lb
      if (lb + 1 < this._heap.length && this._heap[lb].getWeight() < this._heap[lb + 1].getWeight()) {
        toSwap = lb + 1
      }
      if (this._heap[n].getWeight() < this._heap[toSwap].getWeight()) {
        [this._heap[n], this._heap[toSwap]] = [this._heap[toSwap], this._heap[n]]
        // this._heap[n], this._heap[toSwap] = this._heap[toSwap], this._heap[n]
        n = toSwap
      } else {
        break
      }
    }
  }

  private _root(): number {
    return 1
  }

  private _last(): number {
    return this._heap.length - 1
  }

}

export default PriorityQueue
